package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/9
 */

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * 必须原地修改，只允许使用额外常数空间。
 *
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 *
 */
public class NextPermutation {
    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1};
        new NextPermutation().nextPermutation(nums);
        for (int i :nums) {
            System.out.print(i+" ");
        }
    }

    public void nextPermutation(int[] nums) {
        if(null==nums||nums.length<=1)return;
        //从末尾开始找倒序
        int i = nums.length-1;
        int num = nums[i];
        i--;
        while(i>=0&&nums[i]>=num){
            num = nums[i];
            i--;
        }
        //如果i>=0,说明需要交换
        if(i>=0){
            //找出最合适的交换位置
            int len = nums.length-1;
            while(nums[i]>=nums[len]){
                 len--;
            }
            int temp = nums[i];
            nums[i] = nums[len];
            nums[len] = temp;
        }
        //反转 后面的元素
        swap(nums,i+1,nums.length-1);
    }

    private void swap(int[]nums,int i,int j){
        for(int m=i;m<=(i+j)/2;m++){
            int temp = nums[m];
            nums[m] = nums[j-m+i];
            nums[j-m+i] = temp;
        }
    }
}
